from typing import List


class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        tree = AVLTree()

        for i in range(indexDiff):
            if tree.predecessor(nums[i]) is not None and abs(tree.predecessor(nums[i]) - nums[i]) <= valueDiff:
                return True
            if tree.successor(nums[i]) is not None and abs(tree.successor(nums[i])-nums[i]) <= valueDiff:
                return True
            if tree.contains(nums[i]):
                return True
            tree.insert(nums[i])
        for i in range(indexDiff, len(nums)):

            if tree.predecessor(nums[i]) is not None and abs(tree.predecessor(nums[i]) - nums[i]) <= valueDiff:
                return True
            if tree.successor(nums[i]) is not None and abs(tree.successor(nums[i]) - nums[i]) <= valueDiff:
                return True
            if tree.contains(nums[i]):
                return True
            tree.delete(nums[i - indexDiff])
            tree.insert(nums[i])
        return False

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 节点高度


class AVLTree:
    def __init__(self):
        self.root = None

    # 获取高度
    def _get_height(self, node):
        return node.height if node else 0

    # 获取平衡因子
    def _get_balance(self, node):
        return self._get_height(node.left) - self._get_height(node.right) if node else 0

    # 右旋
    def _rotate_right(self, y):
        x = y.left
        T2 = x.right
        x.right = y
        y.left = T2
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
        return x

    # 左旋
    def _rotate_left(self, x):
        y = x.right
        T2 = y.left
        y.left = x
        x.right = T2
        x.height = 1 + max(self._get_height(x.left), self._get_height(x.right))
        y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
        return y

    # 插入
    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if not node:
            return AVLNode(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        else:
            return node  # 不允许重复

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
        balance = self._get_balance(node)

        # 4 种旋转情况
        if balance > 1 and key < node.left.key:  # LL
            return self._rotate_right(node)
        if balance < -1 and key > node.right.key:  # RR
            return self._rotate_left(node)
        if balance > 1 and key > node.left.key:  # LR
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        if balance < -1 and key < node.right.key:  # RL
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

        return node

    # 删除
    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if not node:
            return node
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            temp = self._min_value_node(node.right)
            node.key = temp.key
            node.right = self._delete(node.right, temp.key)

        node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
        balance = self._get_balance(node)

        # 平衡调整
        if balance > 1 and self._get_balance(node.left) >= 0:
            return self._rotate_right(node)
        if balance > 1 and self._get_balance(node.left) < 0:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        if balance < -1 and self._get_balance(node.right) <= 0:
            return self._rotate_left(node)
        if balance < -1 and self._get_balance(node.right) > 0:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)
        return node

    # 查找是否存在
    def contains(self, key):
        return self._contains(self.root, key)

    def _contains(self, node, key):
        if not node:
            return False
        if key < node.key:
            return self._contains(node.left, key)
        elif key > node.key:
            return self._contains(node.right, key)
        else:
            return True

    # 找最小节点
    def _min_value_node(self, node):
        while node.left:
            node = node.left
        return node

    # 找前驱（小于 x 的最大值）
    def predecessor(self, key):
        node = self.root
        pred = None
        while node:
            if node.key < key:
                pred = node.key
                node = node.right
            else:
                node = node.left
        return pred

    # 找后继（大于 x 的最小值）
    def successor(self, key):
        node = self.root
        succ = None
        while node:
            if node.key > key:
                succ = node.key
                node = node.left
            else:
                node = node.right
        return succ

    # 中序遍历（验证用）
    def inorder(self):
        res = []
        self._inorder(self.root, res)
        return res

    def _inorder(self, node, res):
        if node:
            self._inorder(node.left, res)
            res.append(node.key)
            self._inorder(node.right, res)

if __name__ == '__main__':
    s = Solution()
    r = s.containsNearbyAlmostDuplicate(nums = [1,2,3,1], indexDiff = 3, valueDiff = 0)
    print(r)